Sipser–Lautemann theorem

Short description: Bounded-error probabilistic polynomial time is contained in the polynomial time hierarchy

In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ₂ ∩ Π₂.

In 1983, Michael Sipser showed that BPP is contained in the polynomial time hierarchy. Péter Gács showed that BPP is actually contained in Σ₂ ∩ Π₂. Clemens Lautemann contributed by giving a simple proof of BPP’s membership in Σ₂ ∩ Π₂, also in 1983. It is conjectured that in fact BPP=P, which is a much stronger statement than the Sipser–Lautemann theorem.

Proof

Here we present the proof by Lautemann. Without loss of generality, a machine M ∈ BPP with error ≤ 2^−|x| can be chosen. (All BPP problems can be amplified to reduce the error probability exponentially.) The basic idea of the proof is to define a Σ₂ sentence that is equivalent to stating that x is in the language, L, defined by M by using a set of transforms of the random variable inputs.

Since the output of M depends on random input, as well as the input x, it is useful to define which random strings produce the correct output as A(x) = {r | M(x,r) accepts}. The key to the proof is to note that when x ∈ L, A(x) is very large and when x ∉ L, A(x) is very small. By using bitwise parity, ⊕, a set of transforms can be defined as A(x) ⊕ t={r ⊕ t | r ∈ A(x)}. The first main lemma of the proof shows that the union of a small finite number of these transforms will contain the entire space of random input strings. Using this fact, a Σ₂ sentence and a Π₂ sentence can be generated that is true if and only if x ∈ L (see conclusion).

Lemma 1

The general idea of lemma one is to prove that if A(x) covers a large part of the random space [math]\displaystyle{ R= \{ 1,0 \} ^ {|r|} }[/math] then there exists a small set of translations that will cover the entire random space. In more mathematical language:

If [math]\displaystyle{ \frac{|A(x)|}{|R|} \ge 1 - \frac{1}{2^{|x|}} }[/math], then [math]\displaystyle{ \exists t_1,t_2,\ldots,t_{|r|} }[/math], where [math]\displaystyle{ t_i \in \{ 1,0 \} ^{|r|} }[/math] such that [math]\displaystyle{ \bigcup_i A(x) \oplus t_i = R. }[/math]

Proof. Randomly pick t₁, t₂, ..., t_|r|. Let [math]\displaystyle{ S=\bigcup_i A(x)\oplus t_i }[/math] (the union of all transforms of A(x)).

So, for all r in R,

[math]\displaystyle{ \Pr [r \notin S] = \Pr [r \notin A(x) \oplus t_1] \cdot \Pr [r \notin A(x) \oplus t_2] \cdots \Pr [r \notin A(x) \oplus t_{|r|}] \le { \frac{1}{2^{|x| \cdot |r|}} }. }[/math]

The probability that there will exist at least one element in R not in S is

[math]\displaystyle{ \Pr \Bigl[ \bigvee_i (r_i \notin S)\Bigr] \le \sum_i \frac{1}{2^{|x| \cdot |r|}} = \frac{2^{|r|}}{2^{|x| \cdot |r|}} \lt 1. }[/math]

Therefore

[math]\displaystyle{ \Pr [S = R] \ge 1 - \frac{2^{|r|}}{2^{|x| \cdot |r|}} \gt 0. }[/math]

Thus there is a selection for each [math]\displaystyle{ t_1,t_2,\ldots,t_{|r|} }[/math] such that

[math]\displaystyle{ \bigcup_i A(x) \oplus t_i = R. }[/math]

Lemma 2

The previous lemma shows that A(x) can cover every possible point in the space using a small set of translations. Complementary to this, for x ∉ L only a small fraction of the space is covered by [math]\displaystyle{ S=\bigcup_i A(x)\oplus t_i }[/math]. We have:

[math]\displaystyle{ \frac{|S|}{|R|} \le |r| \cdot \frac{|A(x)|}{|R|} \le |r| \cdot 2^{-|x|} \lt 1 }[/math]

because [math]\displaystyle{ |r| }[/math] is polynomial in [math]\displaystyle{ |x| }[/math].

Conclusion

The lemmas show that language membership of a language in BPP can be expressed as a Σ₂ expression, as follows.

[math]\displaystyle{ x \in L \iff \exists t_1,t_2,\dots,t_{|r|}\, \forall r \in R \bigvee_{ 1 \le i \le |r|} (M(x, r \oplus t_i) \text{ accepts}). }[/math]

That is, x is in language L if and only if there exist [math]\displaystyle{ |r| }[/math] binary vectors, where for all random bit vectors r, TM M accepts at least one random vector ⊕ t_i.

The above expression is in Σ₂ in that it is first existentially then universally quantified. Therefore BPP ⊆ Σ₂. Because BPP is closed under complement, this proves BPP ⊆ Σ₂ ∩ Π₂.

Stronger version

The theorem can be strengthened to [math]\displaystyle{ \mathsf{BPP} \subseteq \mathsf{MA} \subseteq \mathsf{S}_2^P \subseteq \Sigma_2 \cap \Pi_2 }[/math] (see MA, SP2).